0975. 奇偶跳【困难】
1. 📝 题目描述
给定一个整数数组 arr，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为偶数跳跃。
你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：
- 在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引
j，使得arr[i] <= arr[j]，且arr[j]的值尽可能小。如果存在多个这样的索引j，你只能跳到满足要求的最小索引j上。 - 在进行偶数跳跃时（如，第 2，4，6... 次跳跃），你将会跳到索引
j，使得arr[i] >= arr[j]，且arr[j]的值尽可能大。如果存在多个这样的索引j，你只能跳到满足要求的最小索引j上。 - （对于某些索引
i，可能无法进行合乎要求的跳跃。）
如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 arr.length - 1），那么该索引就会被认为是好的起始索引。
返回好的起始索引的数量。
示例 1：
txt
输入：[10,13,12,14,15]
输出：2
解释：
从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 arr[2] 是 arr[1]，arr[2]，arr[3]，arr[4] 中大于或等于 arr[0] 的最小值），然后我们就无法继续跳下去了。
从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。
从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
示例 2：
txt
输入：[2,3,1,1,4]
输出：3
解释：
从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：
在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 arr[1] 是（arr[1]，arr[2]，arr[3]，arr[4]）中大于或等于 arr[0] 的最小值。
在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 arr[2] 是（arr[2]，arr[3]，arr[4]）中小于或等于 arr[1] 的最大值。
arr[3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。
在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 arr[3] 是（arr[3]，arr[4]）中大于或等于 arr[2] 的最小值。
我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。
类似地，我们可以推断：
从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
示例 3：
txt
输入：[5,1,3,4,2]
输出：3
解释：
我们可以从起始索引 1，2，4 出发到达数组末尾。1
2
3
4
5
2
3
4
5
提示：
1 <= arr.length <= 200000 <= arr[i] < 100000
2. 🎯 s.1 - 单调栈 + 动态规划
js
/**
* @param {number[]} arr
* @return {number}
*/
var oddEvenJumps = function (arr) {
const n = arr.length
const oddNext = new Array(n).fill(-1) // 奇数跳的下一个位置
const evenNext = new Array(n).fill(-1) // 偶数跳的下一个位置
// 使用单调栈构建跳跃关系
const buildNext = (sortedIndices) => {
const next = new Array(n).fill(-1)
const stack = []
for (const i of sortedIndices) {
while (stack.length > 0 && stack[stack.length - 1] < i) {
next[stack.pop()] = i
}
stack.push(i)
}
return next
}
// 按值升序、索引升序排序，用于奇数跳
const oddSorted = Array.from({ length: n }, (_, i) => i).sort(
(a, b) => arr[a] - arr[b] || a - b,
)
oddNext.splice(0, n, ...buildNext(oddSorted))
// 按值降序、索引升序排序，用于偶数跳
const evenSorted = Array.from({ length: n }, (_, i) => i).sort(
(a, b) => arr[b] - arr[a] || a - b,
)
evenNext.splice(0, n, ...buildNext(evenSorted))
// 动态规划：odd[i] 表示从 i 开始奇数跳能否到达终点
const odd = new Array(n).fill(false)
const even = new Array(n).fill(false)
odd[n - 1] = even[n - 1] = true
// 从后向前遍历
for (let i = n - 2; i >= 0; i--) {
// 如果奇数跳能跳到 j，且从 j 偶数跳能到达终点，则从 i 奇数跳能到达
if (oddNext[i] !== -1) {
odd[i] = even[oddNext[i]]
}
// 如果偶数跳能跳到 j，且从 j 奇数跳能到达终点，则从 i 偶数跳能到达
if (evenNext[i] !== -1) {
even[i] = odd[evenNext[i]]
}
}
// 统计从奇数跳开始能到达终点的起始位置数量
return odd.filter((v) => v).length
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
- 时间复杂度：
- 空间复杂度：
算法思路：
- 预处理跳跃关系：使用单调栈为每个位置预先计算奇数跳和偶数跳的下一个位置
- 奇数跳规则：跳到大于等于当前值的最小值，若有多个则选索引最小的，通过按值升序+索引升序排序后用单调栈构建
- 偶数跳规则：跳到小于等于当前值的最大值，若有多个则选索引最小的，通过按值降序+索引升序排序后用单调栈构建
- 动态规划：
odd[i]表示从位置 i 开始奇数跳能否到达终点，even[i]表示从位置 i 开始偶数跳能否到达终点 - 状态转移：从后向前遍历，
odd[i]依赖于even[oddNext[i]]，even[i]依赖于odd[evenNext[i]] - 结果统计：统计有多少个位置从奇数跳开始能到达终点